package slidingWindow;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class l_30 {
    public static List<Integer> findSubstring(String s, String[] words) {
        //就是438的思路, 实现麻烦了点
        int n1 = s.length(), n2 = words.length, len = words[0].length();
        List<Integer> ans = new ArrayList<>();
        HashMap<String, Integer> hash1 = new HashMap<>(), hash2 = new HashMap<>();
        for(String str: words) hash2.put(str, hash2.getOrDefault(str, 0) + 1);
        for(int i = 0; i < len; ++i)
        {
            //循环条件要加=, 不然最后一个元素不能读取到
            for(int left = i, right = i, count = 0; right + len <= n1; right += len)
            {
                String in = s.substring(right, right + len);
                hash1.put(in, hash1.getOrDefault(in, 0) + 1);
                if(hash1.get(in) <= hash2.getOrDefault(in, 0)) ++count;
                //这里不能加=, 不然滑动窗口内的元素最大只能保持 n2 - 1 了
                if(right - left + 1 > len * n2)
                {
                    String out = s.substring(left, left + len);
                    if(hash1.get(out) <= hash2.getOrDefault(out, 0)) --count;
                    hash1.put(out, hash1.get(out) - 1);
                    left += len;
                }
                if(count == n2) ans.add(left);
            }
            //每一次count和哈希表都要清空
            hash1.clear();
        }
        return ans;
    }
}
